package _02_linked_list.exerc.hascycle;

import _02_linked_list.exerc.ListNode;
import org.junit.Test;

import java.util.Optional;

/**
 * @author: mornd
 * @dateTime: 2023/6/4 - 15:59
 * 判断链表是否有环
 */
public class MyTest {

    /**
     * 构建回环链表
     *
     * @param size       链表长度
     * @param entryIndex 链表环入口的下标
     * @return
     */
    ListNode genericCycleListNode(int size, int entryIndex) {
        ListNode head = null;
        ListNode tail = null;
        // 环入口
        ListNode cycleEntry = null;
        for (int i = 0; i < size; i++) {
            if (head == null) {
                tail = head = new ListNode(i);
            } else {
                ListNode newNode = new ListNode(i);
                tail.next = newNode;
                tail = newNode;
            }
            if (i == entryIndex) {
                cycleEntry = tail;
            }
        }
        tail.next = cycleEntry;
        return head;
    }

    @Test
    public void test() {
        /*
                      -   <-   <-
                      |         |
                      👇        👆
            0 -> 1 -> 2 -> 3 -> 4

         */
        ListNode list = genericCycleListNode(5, -2);
        System.out.println(hasCycle(list));

        Optional<ListNode> opt = detectCycle(list);
        opt.ifPresent(c -> {
            System.out.println(c.val);
        });
    }

    /**
     * 判断链表是否带环
     * 使用龟兔赛跑算法
     * 龟每次走1步，兔每次走两步
     * 兔子走到null处时，不存在环
     * 当兔子追上龟时，即存在环
     *
     * @param n
     * @return
     */
    boolean hasCycle(ListNode n) {
        ListNode rabbit = n;
        ListNode turtle = n;
        // 1,2,3,4,5,6
        while (rabbit != null && rabbit.next != null) {
            rabbit = rabbit.next.next;
            if (rabbit == (turtle = turtle.next)) {
                return true;
            }
        }
        return false;
    }

    /**
     * 查找链表的环入口
     *      兔每次走2步，龟每次走1步
     *      待到兔子追上乌龟，兔子保持原位置不动，龟回到起点
     *      龟继续每次走1步，并且兔子每次也走1步
     *      待到再次相遇时，地点就是环的入口
     *
     * @param n
     * @return 环入口节点，返回 null 表示没有形成环
     */
    Optional<ListNode> detectCycle(ListNode n) {
        ListNode rabbit = n;
        ListNode turtle = n;
        // 是否已相遇
        boolean meet = false;
        while (rabbit != null && rabbit.next != null) {
            rabbit = rabbit.next;
            if(!meet) {
                // 未相遇前，兔子每次蹦俩下，相遇后每次蹦一下
                rabbit = rabbit.next;
            }
            if (rabbit == (turtle = turtle.next)) {
                if(rabbit == n) {
                    // bug 修复，如果相遇节点是头节点，那么环入口就是头节点
                    return Optional.of(rabbit);
                }
                if(meet) {
                    // 第二次相遇，已找到环入口，返回
                    return Optional.of(rabbit);
                } else {
                    // 第一次相遇
                    meet = true;
                    // 乌龟回到起始节点，重新跑
                    turtle = n;
                }
            }
        }
        return Optional.empty();
    }
}
